#pragma once

#include "List.h"

#include "LogManagement.h"
#include "MemoryBase.h"
#include "MemoryStack.h"
#include "MemoryManagement.h"
#include "ContainerBase.h"

#include <assert.h>

namespace EngineLib {

	class _MapELement {
	public:
		_MapELement(void) {}
		~_MapELement(void) {}

	public:
		int _used;
		unsigned int _key;
		void *_value;
		_MapELement *_next;
	};

	template <class T>
	class Map
	{
	private:
		unsigned int _table_size;
		unsigned int _size;
		_MapELement *_data;

	private:
		inline unsigned int _Hash(unsigned int key)
		{
			return key % _table_size;
		}

	public:
		enum MapSize {
			SMALL = 127,
			MEDIUM = 1021,
			LARGE = 8191
		};

	public:
		Map(void) { assert(false); }
		~Map(void) {}

		static Map<T>* New(MemoryStack *memoryStack, MapSize size, MemoryStack::Position left_or_right)
		{
			assert(memoryStack && size);
			unsigned int totalSize = sizeof(Map<T>) + size * sizeof(_MapELement);
			Map<T> *rst = 
				(left_or_right == MemoryStack::LEFT) ?
					((Map<T>*)memoryStack->AllocateLeft(totalSize)) :
					((Map<T>*)memoryStack->AllocateRight(totalSize));
			if (!rst) {
				return 0;
			}
			rst->_table_size = size;
			rst->_size = 0;
			rst->_data = (_MapELement*)(rst + 1);
			memset(rst->_data, 0, rst->_table_size * sizeof(_MapELement));
			return rst;
		}

		unsigned int Size(void)
		{
			return _size;
		}

		bool Insert(unsigned int key, T *value)
		{
			_MapELement *target = &_data[_Hash(key)];
			if (target->_used && target->_key != key) {
				while (target->_next) {
					target = target->_next;
					if (target->_key == key) {
						target->_value = value;
						return true;
					}
				}
				target->_next = (_MapELement*)MemoryManagement::Common128->Allocate();
				target = target->_next;
			}

			target->_used = 1;
			target->_key = key;
			target->_value = value;
			target->_next = 0;

			++_size;

			return true;
		}

		T* Get(unsigned int key)
		{
			if (_size == 0)
				return 0;

			_MapELement *target = &_data[_Hash(key)];

			if (!target->_used)
				return 0;

			do {
				if (target->_key == key) {
					return (T*)target->_value;
				}
				target = target->_next;
			}
			while (target);

			return 0;
		}

		T* Remove(unsigned int key)
		{
			if (_size == 0)
				return 0;

			_MapELement *target = &_data[_Hash(key)];
			_MapELement *temp;
			T* rst;

			if (!target->_used)
				return 0;

			if (target->_key == key) {
				rst = (T*)target->_value;
				if (target->_next) {
					temp = target->_next;
					target->_used = 1;
					target->_key = target->_next->_key;
					target->_value = target->_next->_value;
					target->_next = target->_next->_next;
					MemoryManagement::Common128->Free(temp);
				}

				--_size;

				return rst;
			}

			do {
				if (!target->_next)
					return 0;
				temp = target;
				target = target->_next;
			}
			while (target->_key != key);

			temp->_next = target->_next;

			rst = (T*)target->_value;
			MemoryManagement::Common128->Free(target);

			--_size;

			return rst;
		}

		void Clear(void)
		{
			if (_size == 0)
				return;

			for (unsigned int i = 0; i < _table_size; i++) {
				if (_data[i]._used) {
					_MapELement *cur = &_data[i];
					_MapELement *listcur, *listnext;
					listcur = cur->_next;
					cur->_used = 0;
					cur->_key = 0;
					cur->_value = 0;
					cur->_next = 0;
					while (listcur) {
						listnext = listcur->_next;
						MemoryManagement::Common128->Free(listcur);
						listcur = listnext;
					}
				}
			}

			_size = 0;
		}
	};

}